package 数据结构练习.summer;

import java.util.List;

public class day12 {
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /*
    将两个升序链表合并为一个新的 升序 链表并返回。
    新链表是通过拼接给定的两个链表的所有节点组成的。
    https://leetcode.cn/problems/merge-two-sorted-lists/
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head = new ListNode(), cur = head;
        ListNode cur1 = list1, cur2 = list2;
        while (cur1 != null && cur2 != null) {
            if (cur1.val <= cur2.val) {
                cur.next = cur1;
                cur = cur.next;
                cur1 = cur1.next;
            } else {
                cur.next = cur2;
                cur = cur.next;
                cur2 = cur2.next;
            }
        }
        //过了第一个while循环后至少还存在一个链表有数据
        if (cur1 != null) {
            cur.next = cur1;
        }
        if (cur2 != null) {
            cur.next = cur2;
        }
        return head.next;
    }


    /*
    在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，
    重复的结点不保留，返回链表头指针。 例如，链表 1->2->3->3-
    >4->4->5  处理后为 1->2->5
    https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef?
     */
    //错误解
/*    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead==null)return null;
        ListNode parent=pHead;//记录用于比较的前一个节点方便删除
        ListNode temp=parent.next;//记录用于比较的节点
        ListNode cur=parent.next;//遍历链表
        ListNode t=parent.next;
        while(cur.next!=null){
            cur=cur.next;
            if (temp.val==cur.val){
                if(cur.next==null){
                //如果cur指向了最后一个节点然后也是重复的就直接指向null,再指向next就会越界
                    parent.next=null;
                }else{
                    parent.next=cur.next;
                }
                temp=cur;
            }else{
                t=temp;
                temp=cur;
                //判断cur.next是否等于null主要是防止cur到了最后一个节点再.val越界
                if (cur.next==null||t.val!=cur.next.val){
                    parent=t;
                }
            }
        }
        //判断头节点是不是重复的
        if (pHead.next!=null&&pHead.val==pHead.next.val){
            pHead=pHead.next.next;
        }
        return pHead;
    }*/

    //官方解
    public ListNode deleteDuplication(ListNode pHead) {
        //空链表
        if (pHead == null)
            return null;
        ListNode res = new ListNode(0);
        //在链表前加一个表头
        res.next = pHead;
        ListNode cur = res;
        while (cur.next != null && cur.next.next != null) {
            //遇到相邻两个节点值相同
            if (cur.next.val == cur.next.next.val) {
                int temp = cur.next.val;
                //将所有相同的都跳过
                while (cur.next != null && cur.next.val == temp)
                    cur.next = cur.next.next;
            } else
                cur = cur.next;
        }
        //返回时去掉表头
        return res.next;
    }
}
